﻿#include <iostream>
#include <assert.h>
#include "LFU.h"

template<class T>
DoubledLinkedListNode<T>::DoubledLinkedListNode(T t)
{
	value = t;
	prev = nullptr;
	next = nullptr;
	linkedList = nullptr;
}

template<class T>
T DoubledLinkedListNode<T>::getValue()
{
	return value;
}

template<class T>
void DoubledLinkedListNode<T>::bindLinkedList(DoubledLinkedList<T>* list)
{
	linkedList = list;
}

template<class T>
DoubledLinkedList<T>* DoubledLinkedListNode<T>::getLinkedList()
{
	return linkedList;
}

template<class T>
void DoubledLinkedList<T>::add(DoubledLinkedListNode<T>* node)
{
	if (!head)
	{
		head = node;
		trail = node;
	}
	else
	{
		auto prevTrail = trail;
		trail->next = node;
		node->prev = prevTrail;
		trail = node;
	}

	node->bindLinkedList(this);
}

template<class T>
void DoubledLinkedList<T>::insert(DoubledLinkedListNode<T>* prevNode, DoubledLinkedListNode<T>* node)
{
	assert(prevNode);

	auto next = prevNode->next;
	prevNode->next = node;
	node->prev = prevNode;
	if (next)
	{
		node->next = next;
		next->prev = node;
	}
	else
	{
		trail = node;
	}

	node->bindLinkedList(this);
}

template<class T>
void DoubledLinkedList<T>::remove(DoubledLinkedListNode<T>* node)
{
	if (!head) return;

	if (node == head)
	{
		auto headNext = head->next;
		if (headNext)
		{
			headNext->prev = nullptr;
			head = headNext;
		}
		else
		{
			head = nullptr;
			trail = nullptr;
		}
	}
	else if (node == trail)
	{
		auto trailPrev = trail->prev;
		if (trailPrev)
		{
			trailPrev->next = nullptr;
			trail = trailPrev;
		}
		else
		{
			assert(false && "trail should be the same as head.");
		}
	}
	else
	{
		auto nodePrev = node->prev;
		auto nodeNext = node->next;
		nodePrev->next = nodeNext;
		nodeNext->prev = nodePrev;
	}

	node->prev = nullptr;
	node->next = nullptr;
}

template<class T>
void DoubledLinkedList<T>::setHead(DoubledLinkedListNode<T>* node)
{
	if (!head)
	{
		head = node;
		trail = node;
	}
	else
	{
		node->next = head;
		head->prev = node;
		head = node;
	}

	node->bindLinkedList(this);
}

template<class T>
bool DoubledLinkedList<T>::empty()
{
	return !head;
}

template<class T>
DoubledLinkedListNode<T>* DoubledLinkedList<T>::getHead()
{
	return head;
}

template<class T>
DoubledLinkedListNode<T>* DoubledLinkedList<T>::getTrail()
{
	return trail;
}

template<class T>
DoubledLinkedList<T>::DoubledLinkedList()
{
	head = nullptr;
	trail = nullptr;
}

template<class K, class V>
LFUCache<K, V>::LFUCache(int capacity)
{
	assert(capacity > 0 && "capacity must be more than 0!");
	this->capacity = capacity;
	buckets = new DoubledLinkedList<DoubledLinkedList<K>*>();
}

template<class K, class V>
void LFUCache<K, V>::changeFreqBucket(DoubledLinkedListNode<K>* existNode, int freq)
{
	// 找到该频次的桶
	DoubledLinkedListNode<DoubledLinkedList<K>*>* curFreqBucketHead;
	DoubledLinkedList<K>* nodeList;
	auto freqBucketIt = freqBucketMap.find(freq);
	if (freqBucketIt == freqBucketMap.end())
	{
		nodeList = new DoubledLinkedList<K>();
		curFreqBucketHead = new DoubledLinkedListNode<DoubledLinkedList<K>*>(nodeList);
		nodeList->add(existNode);
		freqBucketMap[freq] = curFreqBucketHead;

		// 如果这个频次是1，即这个key是新加出来的，则直接作为buckets头部即可
		// 如果频次大于1，那这个key之前就存在于cache中，则找(freq-1)这个频次的链表，
		if (freq == 1)
		{
			buckets->setHead(curFreqBucketHead);
		}
		else
		{
			freqBucketIt = freqBucketMap.find(freq - 1);
			assert(freqBucketIt != freqBucketMap.end());
			auto prevNode = freqBucketIt->second;
			buckets->insert(prevNode, curFreqBucketHead);
			nodeList = prevNode->getValue();
			if (nodeList->empty())
			{
				buckets->remove(prevNode);
				freqBucketMap.erase(freq - 1);
				delete(nodeList);
				delete(prevNode);
			}
		}
	}
	else
	{
		auto list = freqBucketIt->second->getValue();
		list->add(existNode);
	}
}

template<class K, class V>
void LFUCache<K, V>::set(K key, V value)
{
	++keyToFreqMap[key];
	auto freq = keyToFreqMap[key];
	DoubledLinkedListNode<K>* existNode;

	if (keyToValueMap.find(key) != keyToValueMap.end())
	{
		existNode = keyToNodeMap[key];
		DoubledLinkedList<K>* list = existNode->getLinkedList();
		// 之前存在的key的node需要先从原链表中移出
		list->remove(existNode);
	}
	else
	{
		existNode = new DoubledLinkedListNode<K>(key);
		keyToNodeMap[key] = existNode;
	}

	keyToValueMap[key] = value;
	changeFreqBucket(existNode, freq);

	if (keyToValueMap.size() > capacity)
	{
		// 删除频次最低的第一个节点
		auto bucketHead = buckets->getHead();
		auto nodeList = bucketHead->getValue();
		auto firstNode = nodeList->getHead();
		auto deleteKey = firstNode->getValue();
		keyToValueMap.erase(deleteKey);
		auto firstFreq = keyToFreqMap[deleteKey];
		keyToFreqMap.erase(deleteKey);
		keyToNodeMap.erase(deleteKey);
		nodeList->remove(firstNode);
		if (nodeList->empty())
		{
			buckets->remove(bucketHead);
			freqBucketMap.erase(firstFreq);
			delete(nodeList);
			delete(bucketHead);
		}

		delete(firstNode);
	}
}

template<class K, class V>
V LFUCache<K, V>::get(K key)
{
	if (keyToValueMap.find(key) == keyToValueMap.end())
	{
		// 没有找到这个key对应的值
		return NULL;
	}

	++keyToFreqMap[key];
	auto freq = keyToFreqMap[key];
	DoubledLinkedListNode<K>* existNode = keyToNodeMap[key];
	DoubledLinkedList<K>* list = existNode->getLinkedList();
	// 之前存在的key的node需要先从原链表中移出
	list->remove(existNode);
	changeFreqBucket(existNode, freq);

	return keyToValueMap[key];
}

template<class K, class V>
bool LFUCache<K, V>::exists(K key)
{
	return keyToValueMap.find(key) != keyToValueMap.end();
}

/**
 * 一个缓存结构需要实现如下功能:
 * void set(int key, int value): 加入或修改key对应的value
 * int get(int key): 查询key对应的value值
 * 
 * 但是缓存中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。
 * 这个策略为: 在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；如果调用次数最少的key有多个，上次调用发生最早的key被删除。
 * 这就是LFU缓存替换算法。实现这个结构，K作为参数给出。
 * 
 * 思路：
 * 使用双向链表，这样在增删节点的时候，可以做到时间复杂度O(1).
 * LFU需要使用二维双向链表，第一维双向链表表示每个频次的桶，第二维双向链表，也就是一维双向链表每个元素表示的桶中存放的具体kv数据，这些kv数据同一频次，构成新的双向链表：
 * 
 * | (k1,v1)  |      | (k4,v4)  |        | (k7,v7)  |
 * |   ↑↓     |		 |   ↑↓     |		 |   ↑↓     |
 * | (k2,v2)  |		 | (k5,v5)  |		 | (k8,v8)  |
 * |   ↑↓     |	---> |   ↑↓     |	---> |   ↑↓     |   --->
 * | (k3,v3)  |	<--- | (k6,v6)  |	<--- | (k9,v9)  |   <--- ...
 * |   ↑↓     |		 |   ↑↓     |		 |   ↑↓     |
 * |  ...     |		 |  ...     |		 |  ...     |
 * |__________|		 |__________|		 |__________|
 *   Freq1             Freq2               Freq3
 * 
 */
int main_lfu()
{
	LFUCache<int, int>* cache = new LFUCache<int, int>(3);
	cache->set(0, 10);
	cache->set(1, 11);
	cache->set(2, 12);
	cache->get(0);
	cache->set(3, 13);
	cache->set(3, 14);
	cache->set(3, 15);
	cache->set(4, 14);

	int key = 1;
	if (cache->exists(key))
	{
		auto target = cache->get(key);
		printf("[%d]=%d\n", key, target);
	}
	else
	{
		printf("key:%d does not exist.\n", key);
	}

	return 0;
}